package com.example.arong;

import java.io.Serializable;
import java.util.*;
import java.util.function.Consumer;

public class ArongLinkedList<E> implements Serializable, Cloneable {

    /**
     * 修改次数
     */
    transient int modCount;

    /**
     * 链表大小
     */
    transient int size = 0;

    /**
     * 头节点
     */
    transient Node<E> first;

    /**
     * 尾节点
     */
    transient Node<E> last;

    private static class Node<E> {
        /**
         * 元素值
         */
        E item;

        /**
         * 后一个节点
         */
        Node<E> next;

        /**
         * 前一个节点
         */
        Node<E> prev;

        public Node(E item, Node<E> next, Node<E> prev) {
            this.item = item;
            this.next = next;
            this.prev = prev;
        }
    }

    /**
     * 构造方法1
     */
    public ArongLinkedList() {

    }

    /**
     * 构造方法2
     * 区别于ArrayList最主要的区别就是没有容量这个说法，所以没有所谓的扩容操作和构造
     * @param c
     */
    public ArongLinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    /**
     * 添加元素到末尾
     * @param e 元素值
     * @return
     */
    public Boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * 添加元素到指定位置
     * @param index 位置
     * @param e 元素值
     */
    public void add(int index, E e) {
        checkPositionIndex(index);
        if(index == size) {
            // 尾部插入情况，同上面方法
            linkLast(e);
        } else {
            linkBefore(e, node(index));
        }
    }



    /**
     * 添加元素到末尾
     * @param e
     */
    private void linkLast(E e) {
        // 记录原有的节点
        final Node<E> l = last;
        // 创建新节点
        // 三个参数为元素值，上一个节点，下一个节点
        final Node<E> newNode = new Node<>(e, l, null);
        // last 指向新节点，与原链表实现连接
        last = newNode;
        if(l == null) {
            // 最后一个节点为空，意味着该链表为空链表，则新节点作为头节点即可
            first = newNode;
        } else {
            l.next = newNode;
        }
        // 增加大小
        size++;
        // 增加修改次数
        modCount++;
    }

    /**
     * 获取 index 位置的节点 二分查找优化
     * @param index
     * @return
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);

        // 如果 index 小于 size 的一半，就正序遍历，获得第 index 个节点
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
            // 如果 index 大于 size 的一半，就倒序遍历，获得第 index 个节点
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    /**
     * 在 succ 节点后新增节点
     * @param e
     * @param succ
     */
    void linkBefore(E e, Node<E> succ) {
        // 获得 succ 的前一个节点
        final Node<E> pred = succ.prev;
        // 创建新的节点 newNode
        final Node<E> newNode = new Node<>(e, pred, succ);
        // <Y> 设置 succ 的前一个节点为新节点
        succ.prev = newNode;
        // 如果 pred 为 null ，说明 first 也为空，则 first 也指向新节点
        if (pred == null)
            first = newNode;
            // 如果 pred 非 null ，说明 first 也为空，则 pred 也指向新节点
        else
            pred.next = newNode;
        // 增加链表大小
        size++;
        // 增加数组修改次数
        modCount++;
    }

    /**
     * 添加元素到对头
     * @param e
     */
    private void linkFirst(E e) {
        // 记录原 first 节点
        final Node<E> f = first;
        // 创建新节点
        final Node<E> newNode = new Node<>(e, f, null);
        // first 指向新节点
        first = newNode;
        // 如果原 first 为空，说明 last 也为空，则 last 也指向新节点
        if (f == null)
            last = newNode;
            // 如果原 first 非空，说明 last 也非空，则原 first 的 next 指向新节点。
        else
            f.prev = newNode;
        // 增加链表大小
        size++;
        // 增加数组修改次数
        modCount++;
    }

    // 下面六个方法是实现 deque 接口之后能够做到的，双端队列
    public void addFirst(E e) {
        linkFirst(e);
    }
    public boolean offerFirst(E e) {
        addFirst(e); // 调用上面的方法
        return true;
    }

    public void addLast(E e) {
        linkLast(e);
    }
    public boolean offerLast(E e) {
        addLast(e); // 调用上面的方法
        return true;
    }
    public void push(E e) {
        addFirst(e);
    }

    public boolean offer(E e) {
        return add(e);
    }

    /**
     * 添加多个元素
     * @param c
     * @return
     */
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    /**
     * 添加多个元素
     * @param index
     * @param c
     * @return
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);

        // 将 c 转成 a 数组
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0) // 如果无添加元素，直接返回 false 数组未变更
            return false;

        // 获得第 index 位置的节点 succ ，和其前一个节点 pred
        Node<E> pred, succ;
        if (index == size) { // 如果 index 就是链表大小，那说明插入队尾，所以 succ 为 null ，pred 为 last 。
            succ = null;
            pred = last;
        } else { // 如果 index 小于链表大小，则 succ 是第 index 个节点，prev 是 succ 的前一个二节点。
            succ = node(index);
            pred = succ.prev;
        }

        // 遍历 a 数组，添加到 pred 的后面
        for (Object o : a) {
            // 创建新节点
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(e, pred, null);
            // 如果 pred 为 null ，说明 first 也为 null ，则直接将 first 指向新节点
            if (pred == null)
                first = newNode;
                // pred 下一个指向新节点
            else
                pred.next = newNode;
            // 修改 pred 指向新节点
            pred = newNode;
        }

        // 修改 succ 和 pred 的指向
        if (succ == null) { // 如果 succ 为 null ，说明插入队尾，则直接修改 last 指向最后一个 pred
            last = pred;
        } else { // 如果 succ 非 null ，说明插入到 succ 的前面
            pred.next = succ; // prev 下一个指向 succ
            succ.prev = pred; // succes 前一个指向 pred
        }

        // 增加链表大小
        size += numNew;
        // 增加数组修改次数
        modCount++;
        // 返回 true 数组有变更
        return true;
    }

    /**
     * 删除指定的元素
     * @param c 集合
     * @return
     */
    public boolean removeAll(Collection<?> c) {
        // 集合的非空校验
        Objects.requireNonNull(c);
        // 标记
        boolean modified = false;
        Iterator<?> it = c.iterator();
        while (it.hasNext()) {
            // 如果 c 中存在该元素，则进行移除
            if(c.contains(it.next())) {
                it.remove();
                modified = true; // 标记修改
            }
        }
        return modified;
    }

    /**
     * 求与指定元素的交集
     * @param c 集合
     * @return
     */
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        // 获得迭代器
        Iterator<?> it = c.iterator();
        // 通过迭代器遍历
        while (it.hasNext()) {
            // <X> 如果 c 中不存在该元素，则进行移除
            if (!c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

    /**
     * 查找某个元素 链表的遍历方式 for
     * @param o
     * @return
     */
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) { // 如果 o 为 null 的情况
            // 顺序遍历，如果 item 为 null 的节点，进行返回
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index; // 找到
                index++;
            }
        } else { // 如果 o 非 null 的情况
            // 顺序遍历，如果 item 为 o 的节点，进行返回
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index; // 找到
                index++;
            }
        }
        // 未找到
        return -1;
    }

    /**
     * 是否包含某个元素
     * @param o 元素
     * @return
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    /**
     * 获取指定位置的值
     * @param index 索引
     * @return
     */
    public E get(int index) {
        checkPositionIndex(index);
        // 基于 node(int index) 方法实现
        return node(index).item;
    }

    /**
     * 设置指定位置的元素
     * @param index 索引
     * @param element 元素值
     * @return
     */
    public E set(int index, E element) {
        checkPositionIndex(index);
        // 获得第 index 位置的节点
        Node<E> x = node(index);
        E oldVal = x.item;
        // 修改对应的值
        x.item = element;
        return oldVal;
    }

    /**
     * 转换成数组
     * @param a
     * @return
     * @param <T>
     */
    public <T> T[] toArray(T[] a) {
        //  如果传入的数组小于 size 大小，则直接复制一个新数组返回
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                    a.getClass().getComponentType(), size);
        // 顺序遍历链表，复制到 a 中
        int i = 0;
        Object[] result = a;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;

        // 如果传入的数组大于 size 大小，则将 size 赋值为 null
        if (a.length > size)
            a[size] = null;

        // 返回 a
        return a;
    }

    public boolean equals(Object o) {
        // 如果 o 就是自己，直接返回 true
        if (o == this)
            return true;
        // 如果不为 List 类型，直接返回 false
        if (!(o instanceof List))
            return false;

        // 创建迭代器，顺序遍历比对
        ListIterator<E> e1 = listIterator();
        ListIterator<?> e2 = ((List<?>) o).listIterator();
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2))) // 如果不相等，返回 false
                return false;
        }
        // 如果有迭代器没有遍历完，说明两者长度不等，所以就不相等；否则，就相等了
        return !(e1.hasNext() || e2.hasNext());
    }

    private ListIterator<E> listIterator() {
        return null;
    }

    /**
     * index 位置校验
     * @param index
     */
    private void checkPositionIndex(int index) {
        if(index < 0 || index > size) {
            throw new IllegalArgumentException("index 错误，index：" + index);
        }
    }

    private class ListItr implements ListIterator<E> {

        /**
         * 最后返回的节点
         */
        private Node<E> lastReturned;
        /**
         * 下一个节点
         */
        private Node<E> next;
        /**
         * 下一个访问元素的位置，从下标 0 开始。
         *
         * 主要用于 {@link #nextIndex()} 中，判断是否遍历结束
         */
        private int nextIndex;
        /**
         * 创建迭代器时，数组修改次数。
         *
         * 在迭代过程中，如果数组发生了变化，会抛出 ConcurrentModificationException 异常。
         */
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            // 获得下一个节点
            next = (index == size) ? null : node(index);
            // 下一个节点的位置
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            // 校验是否数组发生了变化
            checkForComodification();
            // 如果已经遍历到结尾，抛出 NoSuchElementException 异常
            if (!hasNext())
                throw new NoSuchElementException();

            // lastReturned 指向，记录最后访问节点
            lastReturned = next;
            // next 指向，下一个节点
            next = next.next;
            // 下一个节点的位置 + 1
            nextIndex++;
            // 返回 lastReturned
            return lastReturned.item;
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        public E previous() {
            // 校验是否数组发生了变化
            checkForComodification();
            // 如果已经遍历到结尾，抛出 NoSuchElementException 异常
            if (!hasPrevious())
                throw new NoSuchElementException();

            // 修改 lastReturned 和 next 的指向。此时，lastReturned 和 next 是相等的。
            lastReturned = next = (next == null) ? last : next.prev;
            // 下一个节点的位置 - 1
            nextIndex--;
            // 返回 lastReturned
            return lastReturned.item;
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }

        public void remove() {
            // 校验是否数组发生了变化
            checkForComodification();
            // 如果 lastReturned 为空，抛出 IllegalStateException 异常，因为无法移除了。
            if (lastReturned == null)
                throw new IllegalStateException();

            // 获得 lastReturned 的下一个
            Node<E> lastNext = lastReturned.next;
            // 移除 lastReturned 节点
            unlink(lastReturned);
            // 此处，会分成两种情况
            if (next == lastReturned) // 说明发生过调用 `#previous()` 方法的情况，next 指向下一个节点，而 nextIndex 是无需更改的
                next = lastNext;
            else
                nextIndex--; // nextIndex 减一。

            // 设置 lastReturned 为空
            lastReturned = null;
            // 增加数组修改次数
            expectedModCount++;
        }

        private void unlink(Node<E> lastReturned) {
        }

        public void set(E e) {
            // 如果 lastReturned 为空，抛出 IllegalStateException 异常，因为无法修改了。
            if (lastReturned == null)
                throw new IllegalStateException();
            // 校验是否数组发生了变化
            checkForComodification();
            // 修改 lastReturned 的 item 为 e
            lastReturned.item = e;
        }

        public void add(E e) {
            // 校验是否数组发生了变化
            checkForComodification();
            // 设置 lastReturned 为空
            lastReturned = null;
            // 此处，会分成两种情况
            if (next == null) // 如果 next 已经遍历到尾，则 e 作为新的尾节点，进行插入。算是性能优化
                linkLast(e);
            else // 插入到 next 的前面
                linkBefore(e, next);
            // nextIndex 加一。
            nextIndex++;
            // 增加数组修改次数
            expectedModCount++;
        }

        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            // 遍历剩余链表
            while (modCount == expectedModCount && nextIndex < size) {
                // 执行 action 逻辑
                action.accept(next.item);
                // lastReturned 指向 next
                lastReturned = next;
                //  next 指向下一个节点
                next = next.next;
                // nextIndex 加一。
                nextIndex++;
            }
            // 校验是否数组发生了变化
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

    }
}
